Error correcting codes are a technique of correcting an error bit which is caused by noise occurring in a communication channel in a communication system. In a communication system using this technique, instead of transmitting information data from a transmitter, just as they are, a process, which is referred to as encoding, is performed on an information bit sequence d (equation 1) to be transmitted to calculate a parity bit sequence p (equation 2), and a codeword c (equation 3) which is a sequence which is a combination of the information bit sequence d and the parity bit sequence p is transmitted.d=(d1,d2, . . . ,dk)  (1)p=(p1,p2, . . . ,pm)  (2)c=(d1,d2, . . . ,d1,p1,p2, . . . ,pm)  (3)
Although the transmission bit rate drops by a value corresponding to the parity bit sequence p, a receiver can correct or detect an error existing in the received data by performing a process, which is referred to as decoding, by using both the information bit sequence d and the parity bit sequence p.
An LDPC code is an error correcting code defined by a sparse parity-check matrix with few non-zero elements, as shown in FIG. 13. It is assumed hereafter that matrix elements include only 0 and 1. The number of columns of the parity-check matrix corresponds to the number n of bits (code length) of the codeword c, and, in many cases, the number of rows is the number m of parity bits. The number k of bits of the information bit sequence d is k=n−m.
As a conventional technique of encoding an LDPC code, a method of using a lower triangular matrix is disclosed in nonpatent reference 1. According to this method of using a lower triangular matrix, a fundamental matrix operation, which will be mentioned below, is performed on a parity-check matrix first, and elements in the upper right of a submatrix with m rows and m columns (referred to as an m×m submatrix from here on) on a right-hand side of the matrix are set to 0 to acquire a lower triangular matrix as shown in FIG. 14. Then, by using this lower triangular matrix, parity bits are calculated by backward substitution, and encoding is performed.
In this case, the fundamental matrix operation includes: (1) interchanging two rows; (2) interchanging two columns; and (3) adding a row j to a row i (i≠j) by using modulo 2 (i.e., calculating exclusive OR).
In the case of the conventional method of using a lower triangular matrix, by performing the fundamental matrix operation on the parity-check matrix, non-zero elements of the matrix increase, and, as a result, even if the parity-check matrix is sparse, the lower triangular matrix is no longer a sparse matrix. Therefore, in the conventional method of using a lower triangular matrix, the amount of computations increases with increase in non-zero elements.
On the other hand, an encoding method which has been known since long ago separately from the method of using a lower triangular matrix is also disclosed is nonpatent reference 1. According to this encoding method, a fundamental matrix operation is further performed on the above-mentioned lower triangular matrix to make a right-hand side of the matrix be a unit matrix, as shown in FIG. 15. When an m×k submatrix on a left-hand side of this matrix is expressed by Q2, by multiplying the information bit sequence d by the matrix Q2 from the left, the parity bit sequence p can be determined. The matrix Q2 (or a transposed matrix of the matrix Q2) at this time is referred to as a generator matrix.
However, the number of is included in the generator matrix Q2 shown in FIG. 15 is equal to or larger than that in a matrix Q1 shown in FIG. 14 in many cases. Therefore, a problem is that the number of times of exclusive OR is large and the amount of computations is large, like in the case of the above-mentioned conventional method of using a lower triangular matrix.